package leetcode

import kotlinetc.println

//https://leetcode.com/problems/jump-game/
/**
Given an sort.getArray of non-negative integers, you are initially positioned at the first index of the sort.getArray.

Each element in the sort.getArray represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.


[jump]是求达到走的最少步数，而这里是判断是否可以到达。
 */

fun main(args: Array<String>) {

    canJump(intArrayOf(3, 2, 1, 0, 4)).println()
}

/**
 * 在  [jump]的基础上加入  0的判断。因为[jump]给定的是一定可以到达的，这题因为是判断
 * 是否可以达到，所以出现某一步步数最大是0的时候也是无法到达的
 */
fun canJump(nums: IntArray): Boolean {

    if (nums.size == 1) return true

    var currPos = 0
    val destination = nums.size - 1
    val result = arrayListOf<Int>()

    while (currPos < destination) {

        if (nums[currPos] == 0)return false  //当前点步数限制为0也是不可能达到终点的

        val susp = nums[currPos] + currPos
        if (susp >= destination) {
            return true
        } else {
            var k = currPos + 1
            var farest = 0
            while (k <= susp) {
                if (k + nums[k] > farest) {
                    farest = k + nums[k]
                    currPos = k

                    if (farest >= destination) {
                        return true
                    }
                }
                k++
            }


        }

    }

    return false

}